package com.LeeCode;

import java.util.Arrays;


/**
 * 回文串重新排列查询
 */

public class Code2983 {
    public static void main(String[] args) {
        String s = "baebbfab";
        int[][] queries = {{0, 1, 5, 5}};
        System.out.println(Arrays.toString(new Code2983().canMakePalindromeQueries(s, queries)));
    }


    public boolean[] canMakePalindromeQueries(String s, int[][] queries) {
        char[] chars = s.toCharArray();
        int m = chars.length, n = m / 2;

        int[][] sumS = new int[n + 1][26];
        for (int i = 0; i < n; i++) {
            sumS[i + 1] = sumS[i].clone();
            sumS[i + 1][chars[i] - 'a']++;
        }

        int[][] sumT = new int[n + 1][26];
        for (int i = 0; i < n; i++) {
            sumT[i + 1] = sumT[i].clone();
            sumT[i + 1][chars[m - 1 - i] - 'a']++;
        }

        int[] sumNe = new int[n + 1];
        for (int i = 0; i < n; i++) {
            sumNe[i + 1] = sumNe[i] + (chars[i] == chars[m - 1 - i] ? 0 : 1);
        }

        boolean[] ans = new boolean[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int[] query = queries[i];
            int l1 = query[0], r1 = query[1], l2 = m - 1 - query[3], r2 = m - 1 - query[2];
            ans[i] = l1 <= l2 ?
                    check(l1, r1, l2, r2, sumS, sumT, sumNe) :
                    check(l2, r2, l1, r1, sumT, sumS, sumNe);
        }
        return ans;
    }

    private boolean check(int l1, int r1, int l2, int r2, int[][] sumS, int[][] sumT, int[] sumNe) {
        // 检查公共部分
        if (sumNe[l1] > 0 || sumNe[sumNe.length - 1] - sumNe[Math.max(r1, r2) + 1] > 0)
            return false;

        if (r1 >= r2) { // 区间包含
            return Arrays.equals(count(sumS, l1, r1), count(sumT, l1, r1));
        }

        if (l2 > r1) { // 区间不相交
            return sumNe[l2] - sumNe[r1 + 1] <= 0 &&
                    Arrays.equals(count(sumS, l1, r1), count(sumT, l1, r1)) &&
                    Arrays.equals(count(sumT, l2, r2), count(sumS, l2, r2));
        }

        int[] s1 = subtract(count(sumS, l1, r1), count(sumT, l1, l2 - 1));
        int[] s2 = subtract(count(sumT, l2, r2), count(sumS, r1 + 1, r2));

        return s1 != null && s2 != null && Arrays.equals(s1, s2);
    }

    private int[] count(int[][] sumS, int l, int r) {
        int[] ans = sumS[r + 1].clone();
        for (int i = 0; i < 26; i++) {
            ans[i] -= sumS[l][i];
        }
        return ans;
    }

    private int[] subtract(int[] s1, int[] s2) {
        for (int i = 0; i < 26; i++) {
            s1[i] -= s2[i];
            if (s1[i] < 0) {
                return null;
            }
        }
        return s1;
    }
}
